/**
 * @Question.Title: K 连续位的最小翻转次数
 * @Question.No: 995
 * @Author: DQ
 * @Date: 2021-02-05 16:10:39
 * @Description: 
 */
//在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0
//。 
//
// 返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。 
//
// 
//
// 示例 1： 
//
// 输入：A = [0,1,0], K = 1
//输出：2
//解释：先翻转 A[0]，然后翻转 A[2]。
// 
//
// 示例 2： 
//
// 输入：A = [1,1,0], K = 2
//输出：-1
//解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
// 
//
// 示例 3： 
//
// 输入：A = [0,0,0,1,0,1,1,0], K = 3
//输出：3
//解释：
//翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
//翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
//翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 30000 
// 1 <= K <= A.length 
// 
// Related Topics 贪心算法 Sliding Window 
// 👍 57 👎 0

package slidingwindows.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class MinimumNumberOfKConsecutiveBitFlips {
    public static void main(String[] args) {
        Solution solution = new MinimumNumberOfKConsecutiveBitFlips().new Solution();
        int[] A = new int[]{0,0,0,1,0,1,1,0};
        int K = 3;
        System.out.println(solution.minKBitFlips(A, K));


    }
        //leetcode submit region begin(Prohibit modification and deletion)
        class Solution {

            public int minKBitFlips(int[] A, int K) {
                //结果
                int ans = 0;
                // 前 K-1个，如果反转+1，不反转+0
                int flip = 0;
                //窗口，保存前K个是否反转
                Queue<Boolean> isFlip = new LinkedList<>();
                for (int right=0; right < A.length; right++) {
                    //如果窗口中的个数大于等于K，取出队列前面的（相当于最左边的）
                    boolean leftIsFlip = isFlip.size()>=K?isFlip.poll():false;
                    //获取当前right的前K-1个是否反转的和，
                    flip = flip - (leftIsFlip?1:0);
                    //如果flip的奇偶行与A的right的值相同，代表需要反转
                    if((flip&1)==A[right]){
                        //如果说后面的数小于K，则无法反转
                        if(right + K > A.length) return -1;
                        ans++;
                        flip += 1;
                        isFlip.offer(true);
                    }else {
                        isFlip.offer(false);
                    }
                }
                return ans;
            }
            /**
             * 题解：
             * 首先我们可以知道，对于每个位置而言，只有初始状态和总共被反转了多少次决定了
             * 自己最终的状态。另一方面，我们知道每一个长度为K的区间，最多只会被反转一次，
             * 因为两次反转后对最终结果没有影响。基于此，我们从前往后遍历数组，如果遇到一个0，
             * 我们将当前位置开始的长度为k区间的区间反转。如果遇到0时，剩下的区间长度不足K
             * 说明我们没有办法完成反转。但是如果我们每次反转当前区间时，将区间内每个数都取反，
             * 时间复杂度是O(n*k)O(n∗k)的，这样是不够快的。因为我们需要优化一下，
             * 我们再考虑每个位置上的元素，他只会被前面K - 1个元素是否被反转所影响，
             * 所以我们只需要知道前面k - 1个元素总共反转了多少次(更进一步的说我们只关系反转次数的奇偶性)。
             *
             * 我们使用一个队列保存i前面k - 1个位置有多少元素被反转了。
             *
             * 如果队列长度为奇数，那么当前位置的1被变成0了需要反转，如果为偶数，
             * 说明当前位置的0还是0，需要反转。
             *
             * 如果最后k - 1个位置还有0的话说明失败。否则将i加入队列，更新答案。
             *
             * 时间复杂度：每个元素最多被进入队列和出队列一次，所以总的时间复杂度为O(n)O(n)的。
             *
             * 作者：shty
             * 链接：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/guan-fang-da-an-tai-nan-dong-la-hua-dong-chuang-ko/
             */
        }
//leetcode submit region end(Prohibit modification and deletion)

}